import java.util.ArrayList;
import java.util.List;

public class IsValidBST {
    // leetcode 验证二叉搜索树
    // https://leetcode.cn/problems/validate-binary-search-tree/description/?envType=study-plan-v2&envId=top-100-liked
    private List<Integer> list;
    public boolean isValidBST(TreeNode root) {
        list = new ArrayList<>();
        inorder(root);
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i) <= list.get(i-1)) return false;
        }
        return true;
    }

    private void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        list.add(root.val);
        inorder(root.right);
    }

    /**
     * 因为是二叉搜索树，所以我们可以进行中序遍历，并且通过prev来记录前一个节点的值
     */
    private long prev;
    public boolean isValidBST1(TreeNode root) {
        prev = (long)Integer.MIN_VALUE - 1;
        return isValidBSTChild(root);
    }

    private boolean isValidBSTChild(TreeNode root) {
        if(root == null) return true;
        boolean leftJudge = isValidBSTChild(root.left);
        if (!leftJudge) return false;
        if (root.val <= prev) return false;
        prev = root.val;
        return isValidBSTChild(root.right);
    }
}
